๐Ÿ‘ฉโ€๐Ÿ’ป 87694. ์•„์ดํ…œ ์ค๊ธฐ

@Seongukbaek Posted August 12, 2022 ยท Updated August 12, 2022 ยท 5 min read

๋ฌธ์ œ

Programmers - ์•„์ดํ…œ ์ค๊ธฐ

๐Ÿ“ Logic

// ์ฃผ์–ด์ง„ ์‚ฌ๊ฐํ˜• ์ •๋ณด๋ฅผ ์ด์šฉํ•ด ํ…Œ๋‘๋ฆฌ์™€ ๋‚ด๋ถ€ ์ •๋ณด๋ฅผ map์— ํ‘œ์‹œ private void fillMap(int[] rect) { int x1 = rect[0] * 2; int y1 = rect[1] * 2; int x2 = rect[2] * 2; int y2 = rect[3] * 2; // ๋‚ด๋ถ€ ์ƒ‰์น  // -1 : ๋‚ด๋ถ€ // 1 : ํ…Œ๋‘๋ฆฌ for (int i = x1; i <= x2; i++) { for (int j = y1; j <= y2; j++) { if (map[i][j] == -1) continue; map[i][j] = -1; if (i == x1 || i == x2 || j == y1 || j == y2) map[i][j] = 1; } } }
  • ์ฃผ์–ด์ง„ ์‚ฌ๊ฐํ˜• ์ขŒํ‘œ๋ฅผ 2๋ฐฐํ•˜์—ฌ ์ €์žฅํ•œ๋‹ค. ใ„ท ์žํ˜• ๋งŒ๋‚ฌ์„ ๋•Œ ์ ํ”„ํ•˜์ง€ ์•Š๋„๋ก ํ•˜๊ธฐ ์œ„ํ•จ์ด๋‹ค...
private void bfs(int cX, int cY, int iX, int iY) { int[][] dir = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; boolean[][] visited = new boolean[101][101]; Queue<Coor> queue = new LinkedList<>(); queue.add(new Coor(cX, cY)); while(!queue.isEmpty()) { Coor c = queue.poll(); int curX = c.x; int curY = c.y; for (int[] d : dir) { int nX = curX + d[0]; int nY = curY + d[1]; if (!isValid(nX, nY)) continue; if (map[nX][nY] != 1 || visited[nX][nY]) continue; // map์— ๋น„์šฉ ์ €์žฅ map[nX][nY] = map[curX][curY] + 1; if (nX == iX && nY == iY) { // ์ด๋ฏธ ์ €์žฅ๋œ ๊ฐ’์ด ์žˆ๋‹ค๋ฉด, ๋” ์ตœ์†Œ ๊ฐ’์„ ์ €์žฅ answer = Math.min(answer, map[nX][nY]); continue; } visited[nX][nY] = true; queue.add(new Coor(nX, nY)); } } }
  • ๊ทธ์ € BFS, ๋‹ค๋งŒ ํ…Œ๋‘๋ฆฌ์ธ ๋…€์„๋“ค๋งŒ ๊ณจ๋ผ ํƒ์ƒ‰ํ•œ๋‹ค. ์•„์ดํ…œ์„ ์ฃผ์›Œ๋„ ๋” ๋นจ๋ฆฌ ๊ฐ€๋Š” ๋ฐฉ๋ฒ•์ด ์žˆ์„ ์ˆ˜ ์žˆ์œผ๋‹ˆ ๊ณ„์† ํƒ์ƒ‰ํ•œ๋‹ค.

๐Ÿ“„ CODE

์ฝ”๋“œ ๋ณด๊ธฐ/์ ‘๊ธฐ๐Ÿ’ซ
import java.util.*; class Coor { int x; int y; public Coor(int x, int y) { this.x = x; this.y = y; } } class Solution { private static int[][] map = new int[101][101]; private static int answer = Integer.MAX_VALUE; public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) { for (int[] rect : rectangle) fillMap(rect); bfs(characterX * 2, characterY * 2, itemX * 2, itemY * 2); return answer/2; } // ์ฃผ์–ด์ง„ ์‚ฌ๊ฐํ˜• ์ •๋ณด๋ฅผ ์ด์šฉํ•ด ํ…Œ๋‘๋ฆฌ์™€ ๋‚ด๋ถ€ ์ •๋ณด๋ฅผ map์— ํ‘œ์‹œ private void fillMap(int[] rect) { int x1 = rect[0] * 2; int y1 = rect[1] * 2; int x2 = rect[2] * 2; int y2 = rect[3] * 2; // ๋‚ด๋ถ€ ์ƒ‰์น  // -1 : ๋‚ด๋ถ€ // 1 : ํ…Œ๋‘๋ฆฌ for (int i = x1; i <= x2; i++) { for (int j = y1; j <= y2; j++) { if (map[i][j] == -1) continue; map[i][j] = -1; if (i == x1 || i == x2 || j == y1 || j == y2) map[i][j] = 1; } } } private void bfs(int cX, int cY, int iX, int iY) { int[][] dir = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; boolean[][] visited = new boolean[101][101]; Queue<Coor> queue = new LinkedList<>(); queue.add(new Coor(cX, cY)); while(!queue.isEmpty()) { Coor c = queue.poll(); int curX = c.x; int curY = c.y; for (int[] d : dir) { int nX = curX + d[0]; int nY = curY + d[1]; if (!isValid(nX, nY)) continue; if (map[nX][nY] != 1 || visited[nX][nY]) continue; // map์— ๋น„์šฉ ์ €์žฅ map[nX][nY] = map[curX][curY] + 1; if (nX == iX && nY == iY) { // ์ด๋ฏธ ์ €์žฅ๋œ ๊ฐ’์ด ์žˆ๋‹ค๋ฉด, ๋” ์ตœ์†Œ ๊ฐ’์„ ์ €์žฅ answer = Math.min(answer, map[nX][nY]); continue; } visited[nX][nY] = true; queue.add(new Coor(nX, nY)); } } } private boolean isValid(int i, int j) { return i >= 0 && i < 101 && j >= 0 && j < 101; } }

โœ๏ธ Review

  • ์ฒ˜์Œ์—๋Š” ํฐ map ์— ๊ฐ ์ง์‚ฌ๊ฐํ˜• ์ขŒํ‘œ๋“ค์„ ์ถ”๊ฐ€ํ•˜๋ฉด์„œ, ํ…Œ๋‘๋ฆฌ๋Š” 1 , ๋‚ด๋ถ€๋Š” -1 ๋กœ ํ‘œํ˜„ํ•˜์—ฌ ์ „์ฒด ํ…Œ๋‘๋ฆฌ๋Š” ๊ฒฐ๊ตญ 1 ๋กœ๋งŒ ์ด๋ฃจ์–ด์ง€๊ฒŒ ํ–ˆ๋‹ค. ์ดํ›„ 1 ์ธ ์ขŒํ‘œ๋“ค์„ ๋”ฐ๋ผ๊ฐ€๊ฒŒ ํ–ˆ๋Š”๋ฐ, ๋ฐ˜๋ก€๋กœ ์ธํ•ด ์ž˜๋ชป๋จ์„ ์•Œ์•˜๋‹ค.

    • ์‚ฌ์‹ค 2๋ฐฐ๋กœ ํ™•์žฅํ•œ๋‹ค๋Š” ํ’€์ด๋ฅผ ์–ผํ• ๋ดค์ง€๋งŒ ์•„๋ฌด๋ฆฌ ์ƒ๊ฐํ•ด๋„ ๋” ํšจ์œจ์ ์œผ๋กœ ์งค ์ˆ˜ ์žˆ์„ ๊ฒƒ ๊ฐ™์•„์„œ ํ…Œ๋‘๋ฆฌ๋งˆ๋‹ค์˜ ๋ฐฉํ–ฅ์„ ์ €์žฅํ•˜๊ณ  ํƒ์ƒ‰ ์‹œ์— ์‚ฌ์šฉํ•˜๋Š” ๋ฐฉ๋ฒ•๋„ ์ƒ๊ฐํ–ˆ์ง€๋งŒ ๊ฐ€๋งŒํžˆ ์ƒ๊ฐํ•ด๋ณด๋‹ˆ ใ„ท ํ˜•ํƒœ์—์„œ ๋ฌด์กฐ๊ฑด ๋ชฉํ‘œ๋Œ€๋กœ ๋™์ž‘ํ•˜์ง€ ์•Š์„ ๊ฒƒ ๊ฐ™์•˜๋‹ค.
  • ๊ทธ๋ƒฅ ์กŒ๋‹ค. ๋ฉ์ฒญ์ด
@Seongukbaek
๋ฐฐ์šฐ๊ณ  ์ •๋ฆฌํ•˜๊ณ  ๊ณต์œ ํ•˜๋Š” ๋Œ€ํ•™์ƒ ๋ฐฑ์„ฑ์šฑ์ž…๋‹ˆ๋‹ค ๐Ÿ˜€